#define _CRT_SECURE_NO_WARNINGS 1

#include"SeqList.h"

void SeqListInit(SL* psl)
{
	psl->arr = NULL;
	psl->size = 0;
	psl->capacity = 0;
}

void SeqListPrint(SL* psl)
{
	for (int i = 0;i < psl->size;i++)
	{
		printf("%d ", psl->arr[i]);
	}
	printf("\n");
}

void SeqListPushBack(SL* psl, SLDataType x)
{
	//SeqListCheckCpacity(psl);
	//psl->arr[psl->size] = x;
	//psl->size++;
	SeqListInsert(psl, psl->size, x);
}

void SeqListDestroy(SL* psl)
{
	free(psl->arr);
	psl->arr = NULL;
	psl->size = psl->capacity = 0;
}

void SeqListPopBack(SL* psl)
{
	//assert(psl->size > 0);
	//psl->size--;
	SeqListErase(psl, psl->size-1);
}

void SeqListPushFront(SL* psl, SLDataType x)
{
	//SeqListCheckCpacity(psl);
	//int end = psl->size - 1;
	//while (end >= 0)
	//{
	//	psl->arr[end + 1] = psl->arr[end];
	//	end--;
	//}
	//psl->arr[0] = x;
	//psl->size++;
	SeqListInsert(psl, 0, x);
}

void SeqListCheckCpacity(SL* psl)
{
	if (psl->size == psl->capacity)
	{
		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(psl->arr, newcapacity * sizeof(SLDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		psl->arr = tmp;
		psl->capacity = newcapacity;
	}
}

void SeqListPopFront(SL* psl)
{
	//assert(psl->size > 0);
	//int begin = 0;
	//while (begin < psl->size - 1)
	//{
	//	psl->arr[begin] = psl->arr[begin + 1];
	//	begin++;
	//}
	//psl->size--;
	SeqListErase(psl, 0);
}

int SeqListFind(SL* psl, SLDataType x)
{
	for (int i = 0;i < psl->size;i++)
	{
		if (psl->arr[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SL* psl, int pos, SLDataType x)//position 位置
{
	assert(pos >= 0 && pos <= psl->size);
	SeqListCheckCpacity(psl);

	int end = psl->size - 1;
	while (pos <= end)
	{
		psl->arr[end + 1] = psl->arr[end];
		end--;
	}

	psl->arr[pos] = x;
	psl->size++;
}

void SeqListErase(SL* psl, int pos)
{
	assert(pos >= 0 && pos <= psl->size - 1);
	int begin = pos;
	while (begin < psl->size - 1)
	{
		psl->arr[begin] = psl->arr[begin + 1];
		begin++;
	}

	psl->size--;
}

int SeqListLength(SL* psl)
{
	return psl->size;
}

SLDataType SeqListPos(SL* psl, int pos)
{
	assert(pos >= 0 && pos <= psl->size - 1);

	return psl->arr[pos];
}

SL SeqListMerge(SL* psla, SL* pslb)//合并两个顺序表
{
	SL slc;
	SeqListInit(&slc);
	int i = 0, j = 0, k = 0;
	while (psla->size > i && pslb->size > j)
	{
		if (psla->arr[i] < pslb->arr[j])//双指针思想
		{
			SeqListPushBack(&slc, psla->arr[i++]);//把小的插入slc，再让小的下标++，再比较
		}
		else
		{
			SeqListPushBack(&slc, pslb->arr[j++]);
		}
	}
	if (psla->size == i)//如果是psla结束，把pslb剩下的拷到pslc
	{
		while (pslb->size > j)
		{
			SeqListPushBack(&slc, pslb->arr[j++]);
		}
	}
	else//如果是pslb结束，把psla剩下的拷到pslc
	{
		while (psla->size > i)
		{
			SeqListPushBack(&slc, psla->arr[i++]);
		}
	}
	return slc;
}